package com.dylon.sort;

import java.util.Arrays;

/**
 * 插入排序
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] a = new int[]{2,5,3,1,4};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }


    public static void sort(int[] a) {
        int team;
        for (int i=1; i<a.length; i++) {
            System.out.println(Arrays.toString(a));
            team=a[i];
            for (int j=i-1; j>=0; j--) {
                if (a[j]>team) {
                    a[j+1]=a[j];
                    a[j]=team;
                    System.out.println("\t" + Arrays.toString(a));
                } else {
                    System.out.println("\t" + Arrays.toString(a));
                    break;
                }
            }
        }
    }

    /*
    直接插入排序遍历比较时间复杂度是每次O(n),交换的时间复杂度每次也是O(n),那么n次总共的时间复杂度就是O(n^2)。
        折半(二分)插入不能优化成O(nlogn); 因为二分只能减少查找复杂度每次为O(logn),
            而插入的时间复杂度每次为O(n)级别，这样总的时间复杂度级别还是O(n^2)

    具体思想为：
        选取当前位置(当前位置前面已经有序) 目标,就是将当前位置数据插入到前面合适位置。
        向前枚举或者二分查找，找到待插入的位置。
        移动数组，赋值交换，达到插入效果。

    [2, 5, 3, 1, 4]     temp=5
        [2, 5, 3, 1, 4]
    [2, 5, 3, 1, 4]     temp=3
        [2, 3, 5, 1, 4]
        [2, 3, 5, 1, 4]
    [2, 3, 5, 1, 4]     temp=1
        [2, 3, 1, 5, 4]
        [2, 1, 3, 5, 4]
        [1, 2, 3, 5, 4]
    [1, 2, 3, 5, 4]     temp=4
        [1, 2, 3, 4, 5]
        [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 5]

     */
}
